package com.yan_jiu_sheng.LeetCodeHot100.AC;


import java.util.*;

/**
 * https://leetcode.cn/problems/sliding-window-maximum/?envType=study-plan-v2&envId=top-100-liked
 * 通过
 * 了解学习了单调队列的使用
 *
 * @author yulongTian
 * @create 2024-05-27 9:56
 */
public class Test11 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3)));
    }


    /**
     * 单调队列
     *
     * @param nums
     * @param k
     * @return
     */
    public static int[] maxSlidingWindow(int[] nums, int k) {
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        int n = nums.length;
        int[] res = new int[n - k + 1];
        int idx = 0;
        for (int i = 0; i < n; i++) {
            // 根据题意，i为nums下标，是要在[i - k + 1, i] 中选到最大值，只需要保证两点
            // 1.队列头结点需要在[i - k + 1, i]范围内，不符合则要弹出
            while (!deque.isEmpty() && deque.peek() < i - k + 1) {
                deque.poll();
            }
            // 2.既然是单调，就要保证每次放进去的数字要比末尾的都大，否则也弹出
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }

            deque.offer(i);

            // 因为单调，当i增长到符合第一个k范围的时候，每滑动一步都将队列头节点放入结果就行了
            if (i >= k - 1) {
                res[idx++] = nums[deque.peek()];
            }
        }
        return res;
    }


//    /**
//     * 大顶堆超时
//     *
//     * @param nums
//     * @param k
//     * @return
//     */
//    public static int[] maxSlidingWindow(int[] nums, int k) {
//        int len = nums.length;
//        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
//            @Override
//            public int compare(Integer o1, Integer o2) {
//                return o2 - o1;
//            }
//        });
//        if (len <= k) {
//            for (int i = 0; i < len; i++) {
//                priorityQueue.add(nums[i]);
//            }
//            return new int[]{priorityQueue.poll()};
//        }
//        int[] res = new int[len - k + 1];
//
//        for (int i = 0; i < k; i++) {
//            priorityQueue.add(nums[i]);
//        }
//
//        for (int i = k; i < len; i++) {
//            res[i - k] = priorityQueue.peek();
//            priorityQueue.remove(nums[i - k]);
//            priorityQueue.add(nums[i]);
//        }
//        res[len - k] = priorityQueue.poll();
//        return res;
//    }

}
